package hashbuck;

import javax.swing.tree.TreeNode;

public class HashBuck {

    static class Node {
        private int key;
        private int val;
        private Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }

    }

    public Node[] array;
    public int udedsize;

    public HashBuck() {
        array = new Node[10];
    }

    public void put(int key, int val) {
        //找到位置
        int index = key % array.length;
        Node cur = array[index];
        //先遍历检查是否已经有key
        while (cur != null) {
            if(cur.key==key){
                //如果key相等，说明已存在，此时只需要更新value
                System.out.println(-1);
                cur.val=val;
                return;
            }
            cur = cur.next;
        }
        //没有key
        Node node = new Node(key, val);
        //尾插法
//        cur.next = node;
//        udedsize++;
        //头插法
        node.next = array[index];
        array[index] = node;
        udedsize++;

        if(loadFactor() >= 0.75){
            //需要进行扩容散列表的长度
            resize();
        }
    }
    //扩容散列表的长度
    private void resize() {
        //1.新建一个数组
        Node[] tmparr = new Node[array.length*2];

        //2.遍历旧的数组，逐个哈希，找到新的位置
        for (int i = 0; i < array.length; i++) {
            Node cur = array[i];
            while (cur!= null){
                //提前记录下cur.next的位置
                Node curNext = cur.next;
                int newindex = cur.key % tmparr.length;
                //头插法
                cur.next = tmparr[newindex];
                tmparr[newindex] = cur;

                cur = curNext;
            }
        }
        //最关键的一步，不要忘了
        array = tmparr;

    }

    //计算负载因子
    private double loadFactor(){
        return udedsize*1.0 / array.length;
    }

    public int getvalue(int key){
        //先找到位置
        int index  =  key % array.length;

        //在遍历整个链表
        Node cur = array[index];
        while (cur!=null){
            if(cur.key==key){
                return cur.val;

            }
            cur = cur.next;
        }
        return -1;
    }

}
